Loops in the active topology of bridged networks can lead to severe problems including unicast frame duplication, multicast frame duplication, and address table nonconvergence. The inability to tolerate active loops is a fundamental limitation to the topology of bridged networks. Such loops must be eliminated to ensure proper network operation. Generically speaking, two approaches have been taken in the past to eliminate loops: manual and automatic configuration.
Manual configuration simply means to configure the passive topology of the network so as to avoid loops. However, it is not always possible or even desirable to manually configure a loop-free topology. Manual configuration of a loop-free topology is generally only acceptable for small networks. Additionally, even in small networks link redundancy may be necessary and therefore small networks may have loops.
Automatic configuration eliminates loops in the active topology of the network by means of a special computer protocol. An example of a protocol used for eliminating loops in a network is Spanning Tree Protocol (STP). STP was developed as a vendor-independent protocol to solve the problem of network loops and a formal specification of the protocol is contained in the Institute of Electrical and Electronics Engineers (IEEE) 802.01D standard. As defined in the 802.01D standard, the elements of a network that are affected by STP are referred to as the root bridge, designated bridges, root ports, and designated ports. The network elements existing in an STP setting are all part of a “tree” that spans (encompasses) all of the parts of the network without creating any active loops. STP assigns a single path with the lowest path cost between any two endpoints. STP prevents loops from forming by deactivating ports that have a higher path cost than other ports capable of carrying traffic to the same destination.
One disadvantage to applying STP in a geographically large network is that STP tries to calculate a spanning tree (i.e., compute port states) that covers the entire network. Because the entire network is covered by one spanning tree, network resources may be overburdened with carrying STP configuration messages throughout the network STP configuration messages are commonly referred to as Bridge Protocol Data Units (BPDUs). Additionally, typically, network providers and network customers do not desire to share the same spanning tree instance, so having only one spanning tree that covers the entire network, as in the case of STP, is a problem. Furthermore, in a geographically large network, a limitation on the number of hops that a BPDU can take may cause BPDUs to expire before they reach the most distant nodes in the network. Thus, using STP in a large network can tie up valuable resources and result in needless congestion.
FIG. 1 depicts a bridged network 100 that is connected by network nodes 110, 112, 114, 116, 118, and 120, and composed of three ring structures. Applying the known STP protocol, the network would be configured into a single loop-free spanning tree. As depicted in the embodiment of FIG. 1, there are no boundaries within the network 100 to restrict circulation of BPDUs 111, as the BPDUs 111 travel freely throughout the entire network 100. Since the BPDUs 111 travel freely throughout the entire network, there is a delay in communicating traffic through the network while the spanning tree is established. Additionally, since the BPDUs 111 typically have an age (i.e. a maximum number of hops) beyond which they expire, the BPDUs 111 may expire before traveling from the root bridge to the other end of the network. Furthermore, although STP provides a loop-free path, it does not necessarily provide the best or most direct path since STP considers only physical topology and not logical topology (i.e., VLAN)
In an attempt to address the problems associated with STP, per-Virtual Local Area Network Spanning Tree Protocol (PVST) was created. PVST operates in a similar fashion to STP, however, it limits circulation of BPDUs and related spanning tree calculations to within a particular Virtual Local Area Network (VLAN). Although PVST eliminates some of the problems associated with STP, if a VLAN spreads over a large geographical area, then PVST can incur the same types of congestion and BPDU expiration problems as STP. Additionally, since network providers and network customers can share the same VLAN, like STP, PVST does not eliminate the problem of the provider and customer sharing the same spanning tree instance. FIG. 2 depicts a bridged network 200 connected by network nodes 210, 212, 214, 216, 218, and 220, composed of three ring structures and supporting two VLANs, VLAN A, and VLAN B. In the embodiment of FIG. 2, VLAN A is physically separated into two portions that exist on either side of VLAN B. In order to prevent loops within VLAN A, the BPDUs 211 originating in either portion of VLAN A travel throughout all of VLAN A. As depicted in FIG. 2, to reach all of the nodes within VLAN A, the BPDUs 211 must tunnel through VLAN B. Although PVST provides a loop-free and best (most direct) path, PVST has significant drawbacks. Namely, tunneling BPDUs through VLAN B uses network resources to encapsulate and deencapsulate the BPDUs 211. Additionally, tunneling delays packet forwarding and also may cause the BPDUs 211 to expire before they reach the outermost node in VLAN A. When BPDUs expire before reaching the outermost node, the outermost node may assume that it is now the root bridge because the outermost node is no longer receiving messages from the root bridge. If the outermost node believes that it is now the root bridge, then the outermost node will begin to send out BPDUs, leading to increased congestion and confusion in the network.
There is therefore a need for an effective way to prevent loops in a network, and especially a geographically large network.